package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * greedy
 * 649. Dota2 参议院
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/23 13:37
 */
public class PredictPartyVictory {

    public static void main(String[] args) {
        PredictPartyVictory test = new PredictPartyVictory();

        // Radiant
//        String str = "RRDDD";

        // Radiant
//        String str = "RD";

        // Dire
//        String str = "RDDRD";

        // Dire
//        String str = "RDD";


        int l = 10000;
        StringBuilder sb = new StringBuilder(l);
        for (int i = 0; i < l; i++) {
            sb.append(Math.random() > 0.5 ? 'R' : 'D');
        }
        String str = sb.toString();
        System.out.println("\"" + str + "\"");


        String s = test.predictPartyVictory(str);
        System.out.println(s);
    }

    public String predictPartyVictory(String senate) {
        int length = senate.length() - 1;
        char[] arr = senate.toCharArray();
        int ac = 0;
        int bc = 0;
        for (int i = 0; i <= length; i++) {
            char c = senate.charAt(i);
            if (c == 'R') {
                ac++;
            } else {
                bc++;
            }
        }
        int a = 0;
        int b = 0;
        int i = 0;
        int st = 0;
        while (ac != 0 && bc != 0) {
            char c = arr[i];
            if (c == 'R') {
                if (a < 0) {
                    a++;
                } else {
                    b--;
                    arr[st++] = c;
                    bc--;
                }
            } else {
                if (b < 0) {
                    b++;
                } else {
                    a--;
                    arr[st++] = c;
                    ac--;
                }
            }
            i++;
            if (i > length) {
                i = 0;
                length = st - 1;
                st = 0;
            }
        }
        return ac > 0 ? "Radiant" : "Dire";
    }

}
